package 中等.树;

import util.TreeNode;

/**
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder
 * 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构
 * 造二叉树并返回其根节点。
 *
 * @ https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=daily-question&envId=2024-02-20
 * @date 2024/02/25
 */
public class 从前序与中序遍历序列构造二叉树_105 {

    public static void main(String[] args) {

        从前序与中序遍历序列构造二叉树_105 impl = new 从前序与中序遍历序列构造二叉树_105();

        //preorder =
        //[3,9,20,15,7]
        //inorder =
        //[9,3,15,20,7]
        TreeNode treeNode = impl.buildTree(new int[]{1, 2, 3}, new int[]{3, 2, 1});
        System.out.println(treeNode);

    }

    /**
     * 先序遍历：根-左子树-右子树
     * 中序遍历：左子树-根-右子树
     * 思路：先通过先序遍历确定根节点，然后通过中序遍历确定
     * 左子树和右子树，递归下去，类似分治的思想
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);

    }

    /**
     * preorder[preLeft,preRight] 区间是先序遍历数组
     * inorder[inLeft,inRight] 区间是中序遍历数组
     */
    private TreeNode buildTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft < 0 || preRight >= preorder.length || preLeft > preRight) {
            return null;
        }
        if (inLeft < 0 || inRight >= inorder.length || inLeft > inRight) {
            return null;
        }
        if (inLeft == inRight) {
            return new TreeNode(inorder[inLeft]);
        }

        // 根节点
        TreeNode treeNode = new TreeNode(preorder[preLeft]);
        // 在中序遍历数组里面找到根节点，并且将中序遍历中左子树存到哈希表
        int idx = inLeft;
        for (int i = inLeft; i <= inRight; i++) {
            if (inorder[i] == preorder[preLeft]) {
                idx = i;
                break;
            }
        }
        // 先序遍历的左子树数组长度和中序遍历是一样的，可以根据中序遍历的左子树数组长度算出来
        int leftChildCnt = idx - inLeft;

        treeNode.left = buildTree(preorder, inorder, preLeft + 1, preLeft + leftChildCnt, inLeft, idx - 1);
        treeNode.right = buildTree(preorder, inorder, preLeft + leftChildCnt + 1, preRight, idx + 1, inRight);
        return treeNode;
    }

}
